package 数组;

import java.util.HashMap;
import java.util.Map;

/**
 * @author 会玩的洋洋
 * https://leetcode-cn.com/problems/two-sum/
 */
public class _1_两数之和 {

    /**
     * 哈希表  通过一存一取  来对比数据
     * @param nums 目标数组
     * @param target 目标值
     * @return int[]
     */
    public int[] twoSumByHash(int[] nums, int target) {
        int n = nums.length;
        Map<Integer, Integer> hash = new HashMap<>(n);
        hash.put(nums[0], 0);
        for (int i = 1; i < n; i++) {
            if (hash.containsKey(target - nums[i])) {
                return new int[]{hash.get(target - nums[i]), i};
            }
            hash.put(nums[i], i);
        }
        return null;
    }

    /**
     * 暴力解法 O(n^2)
     * @param nums 目标数组
     * @param target 目标值
     * @return int[]
     */
    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        int[] ret = new int[2];
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                int sum = nums[j] + nums[i];
                if (sum == target) {
                    ret[0] = i;
                    ret[1] = j;
                    return ret;
                }
            }
        }
        return ret;
    }
}
